package 剑指Offer._3140;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/10 9:17
 * 复杂链表的复制
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
 * 还有一个 random 指针指向链表中的任意节点或者 null。
 * 算法：链表 + 哈希表
 * 以 key 为旧节点，val 为新节点构建哈希表
 * 对于 random，先将 random 指向的节点构造出来，存放在 map 中
 * ------------------------------------------------------
 * 算法：迭代 + 节点拆分
 */
public class _35 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (!map.containsKey(head)) {
            Node node = new Node(head.val);
            map.put(head, node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        return map.get(head);

    }

    public Node copyRandomList_perfect(Node head) {
        if (head == null) return head;
        // 先复制节点，将旧节点的 next 指向相应的新节点
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = new Node(node.val);
            newNode.next = node.next;
            node.next = newNode;
        }
        // 再复制新节点的 random
        for (Node node = head; node != null; node = node.next.next) {
            Node newNode = node.next;
            newNode.random = node.random != null ? node.random.next : null;
        }
        // 将旧节点的 next 指向原来的 next，新节点的 next 执行新的节点
        Node ans = head.next;
        for (Node node = head; node != null; node = node.next) {
            Node newNode = node.next;
            node.next = newNode.next;
            newNode.next = node.next != null ? node.next.next : null;
        }
        return ans;
    }

}
